package oj.oj_110;

import oj.oj_144.TreeNode;

/**
 * 平衡二叉树
 * https://leetcode.cn/problems/balanced-binary-tree/
 */
public class Solution {
    private int heightOf(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = heightOf(root.left);
        int right = heightOf(root.right);

        return Integer.max(left, right) + 1;
    }

    // O(n^2)
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (isBalanced(root.left) == false) {
            // 左子树不是平衡二叉树
            return false;
        }

        if (isBalanced(root.right) == false) {
            // 右子树不是平衡二叉树
            return false;
        }

        // 比较左右子树的高度差
        int left = heightOf(root.left);
        int right = heightOf(root.right);
        int diff = left - right;

        if (diff < -1 || diff > 1) {
            // 绝对值 > 1
            return false;
        }

        return true;
    }
}
